class Solution:
    def searchInsert(self, nums, target: int) -> int:
        if len(nums) == 0:
            return 0
        start = 0
        end = len(nums)
        while start< end:
            mid = (start+end) //2
            if nums[mid]==target:
                return mid
            elif nums[mid]<target:
                start = mid+1

            else:
                end = mid
        return start



if __name__ == '__main__':
    so = Solution()
    n = [1,3,5,6]
    target = 4
    r = so.searchInsert(n, target)
    print(r)
